Introduction to Machine Learning

Unit 18: Regularized Regression + Gradient Boosting

1. Introduction

Standard linear regression minimizes only the training error and has no incentive to prefer simpler models. The result: complex models with huge coefficients overfit and fail to generalize. In the first half of this unit, we study Regularized Regression — Ridge, Lasso, and Elastic Net — which add a penalty term to the loss function to explicitly trade off performance vs. complexity. In the second half, we introduce Gradient Boosting, one of the most powerful off-the-shelf algorithms for tabular regression and classification.

Learning Objectives

2. Theory

2.1 Regularization Motivation

Consider two candidate models that both fit the training data equally well:

Model 1 (Simple)Model 2 (Complex)
\( \hat{y} = 2x_3 + 1.4x_7 - 0.5x_9 + 4 \) \( \hat{y} = 22x_1 - 103x_2 - 14x_3 + 109x_4 - 93x_5 + 203x_6 + 87x_7 - 55x_8 + 378x_9 - 25x_{10} + 8 \)

We should prefer Model 1 — simpler, sparser, with smaller coefficients. Why are large / many coefficients problematic?

  1. Overfitting: The model memorizes training noise instead of true signal.
  2. Poor generalization: Complex models perform worse on unseen data.
  3. Sensitivity: Large coefficients amplify tiny feature variations and noise.
  4. Interpretability: 10 large coefficients are much harder to reason about than 3 small ones.

Solution: Add a regularization term to the cost function that penalizes coefficient magnitude. The result: the optimizer is forced to trade off low training error for model simplicity.

2.2 L1 and L2 Norms

Two mathematical ways to penalize coefficient magnitude. Note: only the weights \( \theta_1, \ldots, \theta_p \) are regularized — never the bias \( \theta_0 \).

L1 Norm (Sum of |·|)
L2 Norm (Sum of squares)
\[ \|\theta\|_1 = \sum_{j=1}^{p-1} |\theta_j| \]

Used in Lasso Regression. Produces sparse solutions (some coefficients become exactly zero).

\[ \|\theta\|_2^2 = \sum_{j=1}^{p-1} \theta_j^2 \]

Used in Ridge Regression. Shrinks all coefficients towards zero (none hit exactly zero).

Numerical Example: L1 vs. L2 Magnitude

Model 1: \( \hat{y} = 2x_3 + 1.4x_7 - 0.5x_9 + 4 \) (weights: 2, 1.4, −0.5; bias 4, not penalized)

Model 2: weights = [22, −103, −14, 109, −93, 203, 87, −55, 378, −25]

Notice how the L2 penalty explodes quadratically for Model 2 — Ridge will really hate Model 2!

2.3 Balancing Performance and Complexity: The Full Cost Function

The total loss is the sum of (a) regression error (quality of fit) and (b) a regularization term (penalty for complexity):

\[ J(\theta) = \text{MSE-error}(\theta) + \lambda \cdot \text{Regularization}(\theta) \]

The hyperparameter \( \lambda \) (lambda) controls the balance between performance and simplicity.

2.4 Ridge vs. Lasso Regression

AspectRidge Regression (L2)Lasso Regression (L1)
Full Cost Function \( J = \frac{1}{2m}\sum(\hat{y}_i-y_i)^2 + \lambda \sum_{j=1}^{p-1} \theta_j^2 \) \( J = \frac{1}{2m}\sum(\hat{y}_i-y_i)^2 + \lambda \sum_{j=1}^{p-1} |\theta_j| \)
Effect on coefficients Shrinks all coefficients toward zero; none set to exactly zero Shrinks and sparsifies: some coefficients become exactly zero
Feature selection Retains all features (still uses them all in predictions) Automatic feature selection (Embedded method!); zeroed-out features are dropped
Interpretability Less interpretable (all p features remain) More interpretable (sparse, fewer non-zero coefficients)
Standardization Strongly recommended (L2 penalty is very scale-sensitive) Recommended (if skipped, regularization is applied unevenly across features)

2.5 Tuning the Regularization Parameter λ

Trying to make the model perform better can make it more complex, and vice versa. \( \lambda \) is the "knob" that resolves this tension:

2.6 Elastic Net

Elastic Net combines both penalties. A hyperparameter \( \rho \in [0, 1] \) (rho) weights the L1 and L2 terms:

\[ J(\theta) = \frac{1}{2m}\sum_{i=1}^{m} (h_\theta(x_i) - y_i)^2 + \lambda \left[ \rho \sum_{j=1}^{p-1} |\theta_j| + (1-\rho) \sum_{j=1}^{p-1} \theta_j^2 \right] \]

Library notation note: In scikit-learn the mixing parameter is called l1_ratio (α in some textbooks). We use \( \rho \) here to avoid confusion with the gradient-descent learning rate α.

2.7 Gradient Boosting — Overview

Gradient Boosting (Friedman, 2001) is a very popular ensemble method that combines multiple decision trees into a stronger model. The core idea is shared with AdaBoost: each weak learner tries to fix the mistakes of previous learners.

AdaBoost vs. Gradient Boosting

AspectAdaBoostGradient Boosting
What gets "boosted"Instance weights of misclassified pointsResiduals (actual y − prediction of previous ensemble)
Weak-learner depthStumps (depth = 1) typicallyDepth 2–8 is common; you set max_depth
Prediction combinationWeighted vote (per-tree α)Additive: each tree's prediction is multiplied by a learning rate ν and summed

2.8 Gradient Boosting — The Worked Example

Dataset of Age vs. Engagement score. We'll set: number of trees = 5 (so 4 additive trees), learning rate ν = 0.8, tree depth ≤ 2.

AgeEngagement (y)
107
205
307
401
502
601
705
804

Step 1: First Weak Learner (Depth 0 — The Mean)

The first "tree" is the simplest model: a single node that predicts the mean label for every point. Mean engagement = (7+5+7+1+2+1+5+4)/8 = 32/8 = 4.

\[ \hat{y}_{\text{tree 1}} = 4 \quad (\text{for all points}) \]

Step 2: Second Weak Learner — Fit to Residuals

The residual = true y minus current prediction. We train a regression tree of depth ≤ 2 to predict these residuals (the gaps Tree 1 failed to fill).

Agey\( \hat{y}_1 \)Residual (\( y - \hat{y}_1 \))\( \hat{y}_{\text{tree 2}} \)
1074+33
2054+12
3074+32
4014−3−2.667
5024−2−2.667
6014−3−2.667
7054+1+0.5
80440+0.5

Step 3: Combine with the Learning Rate ν = 0.8

To avoid overfitting, we don't add Tree 2's full predictions. Instead, we multiply them by the learning rate before summing:

\[ \hat{y}_{1+2} = \hat{y}_{\text{tree 1}} + \nu \cdot \hat{y}_{\text{tree 2}} \]
y\( \hat{y}_1 \)\( \hat{y}_2 \)\( 0.8 \cdot \hat{y}_2 \)\( \hat{y}_{1+2} \)New Residual (\( y - \hat{y}_{1+2} \))
7432.46.4+0.6
5421.65.6−0.6
7421.65.6+1.4
14−2.667−2.131.87−0.87
24−2.667−2.131.87+0.13
14−2.667−2.131.87−0.87
54+0.5+0.44.4+0.6
44+0.5+0.44.4−0.4
GBM Ensemble Additive Process A visual sequence showing a mean prediction followed by progressively smaller residual corrections from five decision trees, resulting in a final prediction. GBM Ensemble Additive Process Each tree learns the remaining error and adds a smaller correction to the ensemble prediction ADDITIVE PREDICTION FLOW STARTING POINT ŷ₁ = 4 global mean baseline TREE 2 + 0.8 × ŷ_tree_2 learn residuals largest correction TREE 3 + 0.8 × ŷ_tree_3 learn new residuals smaller correction TREE 4 + 0.8 × ŷ_tree_4 repeat refinement smaller correction TREE 5 + 0.8 × ŷ_tree_5 continue learning smaller correction ENSEMBLE OUTPUT = final ŷ combined prediction all corrections summed Why do later trees contribute less? Errors shrink after each correction, so subsequent trees predict much smaller adjustments while the learning rate of 0.8 controls how strongly each residual is added.

2.9 Iteratively Building the Full Ensemble

We repeat the process: fit a new regression tree to the latest residuals, multiply its prediction by ν, add to the running total, recompute residuals, and continue. After many trees, the residuals get smaller and smaller — later weak learners only need to make tiny corrections, which is exactly what we want for stable generalization.

2.10 Gradient Boosting Hyperparameters

HyperparameterWhat it controlsGuidance
n_estimators Total number of trees in the ensemble (model complexity) More trees → more complex (can overfit). Unlike Random Forests, more is NOT always better. Tune with learning_rate.
learning_rate (ν) How strongly each tree corrects the mistakes of the previous trees High ν → aggressive corrections, more complex fit. Low ν → slower, need more trees but often better generalization. Typical: 0.01–0.3.
max_depth Max depth per individual tree (pre-pruning) Controls complexity of each learner. Too deep → overfitting on its own. Typical: 2–8.

Common practice: Fix n_estimators given your time/memory budget, then search over learning_rate values via cross-validation. Smaller learning rates usually need more trees — the two are coupled.

Scikit-learn Usage

(For reference / labs. Not executed here.)

Gradient Boosting Regressor workflow A four-step workflow showing import, model configuration, fitting, and prediction using GradientBoostingRegressor. Gradient Boosting Regressor A compact scikit-learn workflow for training an additive ensemble and generating predictions from sklearn.ensemble import GradientBoostingRegressor 1 Import estimator LIBRARY sklearn.ensemble Load the regressor class before defining the model. Python API 2 Configure model HYPERPARAMETERS max_depth = 2 n_estimators = 4 learning_rate = 0.8 Build the ensemble blueprint. 3 Fit the model TRAINING model.fit( features, labels) Learn patterns from features and target labels. TRAIN 4 Generate predictions INFERENCE predictions = model.predict(features) Estimate outputs for the supplied feature set. OUTPUT How the ensemble grows 4 additive trees refine the initial mean prediction; each contribution is scaled by a learning rate of 0.8. shallow trees · depth 2

3. Interactive Examples

Example 1: λ Edge Cases

A. What model do we recover when λ = 0 in Ridge regression?

Ordinary Least Squares (OLS) / standard Linear Regression. The entire regularization term cancels out: \( \lambda = 0 \implies J = \text{MSE only} \). You'll get the same coefficients as the Normal Equation solution.

B. What happens as λ → +∞ in Lasso regression?

The regularization term dominates the loss. The optimum is to set ALL weights \( \theta_1, \ldots, \theta_p \) to exactly zero. The model then predicts only the bias (the mean y of the training set), regardless of the input features. This is an underfit model — use cross-validation to pick a finite λ!

Example 2: Ridge or Lasso?

Pick the more appropriate regularization method for each goal.

Scenario A: You have 500 features and suspect only 20 of them matter; your stakeholders want a short, human-readable list of "the drivers" to put in a report.

Lasso. Its L1 penalty will zero out many of the 480 irrelevant features, giving you the sparse, interpretable shortlist stakeholders need.

Scenario B: You have 20 carefully chosen features from domain experts; each is known to be important. You just want to dampen coefficients and avoid overfitting, without dropping any feature.

Ridge. All 20 features remain with shrunk but non-zero coefficients, respecting the domain knowledge that each feature contributes meaningfully.

Example 3: Gradient Boosting Learning Rate

A student sets learning_rate = 0.999 (essentially no shrinkage) and n_estimators = 1000. They get a training RMSE of 0.0001 but a validation RMSE that's huge. What happened, and how do you fix it?

Diagnosis: Extreme overfitting. With ν ≈ 1, each tree adds its FULL residual correction. 1,000 deep trees memorize every training point exactly (hence RMSE ≈ 0 on train), producing a spiky, non-generalizing model.

Fix:

  1. Lower learning_rate drastically: try 0.1 or 0.01.
  2. Limit individual tree complexity: set max_depth = 3–5.
  3. Pick n_estimators by monitoring validation score (early-stopping style) rather than setting it arbitrarily high.

4. Numerical Solutions

Problem 1: Elastic Net Penalty Term

Weights: \( \theta = [\theta_1 = 3,\ \theta_2 = -4]^T \). λ = 0.1, ρ = 0.6.

📘 Compute the total Elastic Net penalty value

Step 1: L1 part (weighted by ρ):

\[ \rho \sum |\theta_j| = 0.6 \cdot (|3| + |-4|) = 0.6 \cdot 7 = 4.2 \]

Step 2: L2 part (weighted by 1 − ρ):

\[ (1-\rho) \sum \theta_j^2 = 0.4 \cdot (3^2 + (-4)^2) = 0.4 \cdot 25 = 10 \]

Step 3: Multiply by λ and sum:

\[ \lambda(\text{L1-part} + \text{L2-part}) = 0.1 \cdot (4.2 + 10) = \mathbf{1.42} \]

Problem 2: Ridge-Adjusted Normal Equation

Adding L2 regularization to the Normal Equation changes the closed-form solution to:

\[ \theta_{\text{ridge}} = (X^T X + \lambda I')^{-1} X^T y \]

where \( I' \) is the identity matrix but with \( I'_{00} = 0 \) (bias is not regularized). Prove / reason: "Why does adding \( \lambda I' \) guarantee invertibility, even when \( X^T X \) is singular?"

📘 Step-by-Step Reasoning

Step 1: \( X^T X \) is always positive semi-definite: for any vector v, \( v^T X^T X v = \|Xv\|^2 \ge 0 \).

Step 2: Singularity ⟺ some non-zero v exists with \( \|Xv\| = 0 \) (i.e., X has linearly dependent columns).

Step 3: Adding \( \lambda I' \) (with λ > 0 and the bias trick) to \( X^T X \) shifts every eigenvalue of the feature-submatrix by λ. The result is positive definite:

\[ v^T (X^T X + \lambda I') v = \|Xv\|^2 + \lambda \sum_{j \ge 1} v_j^2 > 0 \quad \forall v \ne 0 \]
Positive definite matrices are always invertible. ✓ This is one of Ridge's greatest practical benefits: it fixes multicollinearity / non-invertibility for free.

Problem 3: Gradient Boosting Two-Tree Manual Ensemble

One data point: y = 10. Tree 1 predicts mean = 5. Tree 2 predicts the residual (+5) perfectly. Learning rate ν = 0.2.

📘 Compute ensemble prediction and new residual

Step 1: Combined prediction after 2 trees:

\[ \hat{y}_{1+2} = \hat{y}_1 + \nu \cdot \hat{y}_2 = 5 + 0.2 \cdot 5 = 5 + 1 = \mathbf{6} \]

Step 2: New residual (which Tree 3 will try to correct):

\[ r_3 = y - \hat{y}_{1+2} = 10 - 6 = \mathbf{+4} \]

Even though Tree 2 perfectly predicted the +5 residual, we only add 20% of its correction on purpose. This "slow walk" to the answer is what prevents overfitting — each new tree only takes a small step toward reducing the residual.

5. Try It Yourself

Problem 1 — Ridge vs. Lasso: Compute Penalty Values

Two models with the same 3 non-bias weights: θ = [5, 0, −5].

  1. Compute the L1 penalty term \( \sum |\theta_j| \).
  2. Compute the L2 penalty term \( \sum \theta_j^2 \).
  3. Which penalty method "dislikes" this weight vector more (i.e., produces a bigger numeric penalty)?
  1. L1 = |5| + |0| + |−5| = 10
  2. L2 = 5² + 0² + (−5)² = 25 + 0 + 25 = 50
  3. L2 (Ridge) penalizes it 5× more because it squares the large ±5 weights. L2 disproportionately hates big coefficients, which is exactly why it shrinks them.
Problem 2 — Gradient Boosting Hyperparameter Tradeoffs

For each pair, which setting generally yields a more complex / overfitting-prone model?

  1. n_estimators = 50 vs. n_estimators = 5000
  2. max_depth = 2 vs. max_depth = 20
  3. learning_rate = 0.001 vs. learning_rate = 0.5
  1. 5000 trees → more complex (many more additive terms to memorize noise).
  2. max_depth = 20 → each individual tree is allowed to fragment the data into tiny leaves, massively overfitting within each tree.
  3. learning_rate = 0.5 → each tree's corrections are added aggressively, so the ensemble converges (and then overfits) in far fewer trees. Low ν forces the model to learn slowly and steadily, which usually generalizes better.
Problem 3 — Elastic Net Corner Cases

Elastic Net penalty with λ = 0.5.

  1. If ρ = 0, what method does Elastic Net reduce to? Write its penalty expression using θ = [3, 4].
  2. If ρ = 1, what method does Elastic Net reduce to? Write its penalty expression using θ = [3, 4].
  3. For a given finite λ > 0, which of ρ = 0 vs. ρ = 1 is guaranteed to produce at least one exactly zero coefficient when there are many irrelevant features?
  1. Ridge (only L2): \( 0.5 \cdot (3^2 + 4^2) = 0.5 \cdot 25 = 12.5 \).
  2. Lasso (only L1): \( 0.5 \cdot (|3| + |4|) = 0.5 \cdot 7 = 3.5 \).
  3. ρ = 1 (Lasso). L1 geometry creates corners at the axes of the parameter space, so optima land exactly on them (some θⱼ = 0). Ridge (ρ = 0) never produces exactly zero coefficients — only shrinks them toward zero.

6. Interactive Quiz

Your score: 0 / 5

7. Key Takeaways

  1. Two regularization norms: L1 = sum |θⱼ| → sparse solutions (Lasso). L2 = sum θⱼ² → shrinkage toward zero (Ridge). Bias θ₀ is NEVER regularized.
  2. Full cost: J = MSE + λ·Regularization. λ = 0 recovers OLS; large λ underfits; optimal λ via cross-validation.
  3. Ridge vs. Lasso: Ridge keeps all features (good when all are useful). Lasso zeros some out automatically (embedded feature selection + interpretability).
  4. Elastic Net interpolates Ridge ↔ Lasso with ρ mixing parameter. In practice, ρ = 0.5 often performs best when features are collinear.
  5. Gradient Boosting builds a sequence of trees: Tree 1 predicts the mean; Tree 2+ predict residuals and are summed with a small learning rate ν. Smaller corrections at each step = better generalization.
  6. 3 key GBM hyperparameters: n_estimators (# trees), max_depth (per-tree complexity), learning_rate ν (shrinkage). They must be tuned together via CV — they are tightly coupled.

8. Common Pitfalls

  1. Applying Lasso without standardizing features first. Feature in "dollars" (large values) gets far more L1 penalty than the same feature in "millions of dollars" (tiny values). Always standardize before any penalized regression.
  2. Tuning λ on the test set. Tuning any hyperparameter on the test set leaks information and produces inflated, misleading scores. Use cross-validation on the training set only.
  3. Forgetting that in scikit-learn, n_estimators=4 means 4 additive trees (+ the initial mean in GBM). Off-by-one errors between "number of weak learners" and "number of additive stages" are easy in exam questions.
  4. Using an aggressive learning_rate (0.5+) on large-data GBM and wondering why validation loss plateaus early. Small ν (0.01–0.1) + many trees + early stopping is almost always the winning recipe.
  5. Assuming "Lasso is always better because it does feature selection." When all features are legitimately useful, Lasso's zeroing actually hurts performance by dropping signal. Ridge (or Elastic Net with low ρ) can win here.
  6. Calling Elastic Net a "third separate norm." It's just a weighted combination of L1 and L2 — not a fundamentally new penalty shape. The ρ parameter just dials between the two known extremes.

9. Resources